	\section{Otimização de Código em C e C++}
	\subsection{Introdução}
	\paragraph{}A otimização é um importante e difícil processo no desenvolvimento de um software. Sua aplicação deve ser feita com sabedoria, no momento certo e da maneira correta em um projeto. A sua má aplicação pode levar a programas com bugs, má legibilidade e de difícil manutenção, e não tão eficientes quanto o esperado; Já a sua boa aplicação pode trazer programas eficientes evitando ainda os problemas mencionados anteriormente.

	\subsection{O Momento Certo}
	\paragraph{}Em rigor, o processo de otimização deve ser aplicado no momento em que o código já possui uma certa estabilidade e já é certo que não necessita de muitas modificações. Isso porque, otimizando muito prematuramente, partes do código que seriam descartadas no futuro acabam sendo modificadas.
	
	\subsection{Como otimizar?}
	\paragraph{}Nesta subseção serão abordadas más e boas estratégias de otimização, e na seção seguinte, técnicas importantes de implementação. A maneira como otimizamos um código reflete diretamente nas modificações futuras do mesmo, portanto é importante a escolha da estratégia certa.
	
	\subsubsection{Más Estratégias}
	\begin{itemize}
	\item Assumir que algumas operações são mais rápidas que outras. Não devemos assumir \textbf{nada} quando se trata de otimização. O correto é utilizar um profiler para determinar os pontos críticos do programa;
	\item Reduzir o código para aumentar o desempenho. Geralmente o que acontece é o contrário, o desempenho aumenta aumentando-se o número de linhas de código;
	\item Otimizar a medida que codifica. Otimização é um dos último passos do projeto, pois como mencionado anteriormente, é melhor se aplicada em um código estável;
	\item Concentrar-se demais na performance, esquecendo-se do fato de o código estar correto ou sua completude.
	\end{itemize}
	
	\subsubsection{Boas Estratégias}
	\begin{itemize}
	\item Definir metas específicas para a performance desejada do programa, pensando quantitativamente, como valores em milisegundos. Tentar imaginar qual o tempo de resposta, o frame rate esperado ou outros atributos importantes do programa;
	\item Escolher uma arquitetura apropriada para o problema;
	\item Escolher as estrutura de dados certas para solucionar o problema, estudar a complexidade de espaço e as possibilidades de estruturas de dados para modelar o problema;
	\item Escolher o algoritmo certo, estudar suas complexidades para determinar qual a melhor opção para o problema;
	\item Concentrar na performance que pode ser percebida, não dando atenção apenas aos números, ou seja, mesmo que os valores não sejam aqueles esperados ou estimados, é possível encontrar formas para melhorar mesmo que os valores não mudem;
	\item Entender o custo das operações mais comuns realizadas pelos processadores;
	\item Utilizar um profiler para encontrar gargalos no códigos. O profiler provê informações importantes sobre as diversas partes do programa e o custo para realizá-las;
	\item Checar se as modificações realizadas realmente trouxeram um benefício razoável em relação ao custo anterior das operações;
	\item Como dito anteriormente, avaliar uma versão estável do código, ou a versão que está próxima da versão final;
	\item Automatizar o uso do profiler.
	\end{itemize}
	
	
	\section{Técnicas de Otimização}
	\paragraph{}Nesta seção, serão mencionadas várias técnicas que podem ser utilizadas diretamente para otimizar os códigos em C e C++. Estas técnicas são baseadas na forma como o compilador traduz o código em C ou C++ para a linguagem de máquina e a forma como a máquina interpreta o código traduzido. Algumas dessas técnicas podem ser utilizadas a medida que o programador codifica. Outras mais avançadas são melhores que sejam aplicadas mais tardiamente no projeto.
	
	\subsection{Estrutura de Dados}
	\begin{itemize}
	\item \textbf{Ajustar o tamanho dos registros para uma potência de 2.} Quando existem vetores de registros, a indexação ocorre com uma multiplicação pelo tamanho do registro. Se este tem um tamanho que é potência de 2, a multiplicação é substituída por uma operação de 'shift', que é mais barata que uma multiplicação;
	\item \textbf{Prefira o tipo 'int' aos tipos 'char' e 'short'.} As operações aritméticas e passagem de parâmetros é feita no nível de inteiros, por isso, as variáveis do tipo 'char' e 'short' sofrem conversões (extensão de sinal) antes e depois dessas operações. Para uma operação aritmética de soma, por exemplo, para um 'int' são necessárias seis operações, e para um 'char', onze operações;
	\end{itemize}
	
	\subsection{Funções}
	\begin{itemize}
	\item \textbf{Usar a notação de vetor ao invés da notação de ponteiro quando trabalha com vetores.} A notação de vetor é menos ambígüa, tornando portanto mais fácil para o compilador otimizar o código;
	\item \textbf{Reduzir o número de parâmetros.} Os parâmetros são colocados em uma pilha a cada chamada de função, por isso, quanto maior o número de parâmetros, mais custosa é a chamada de uma função.
	\item \textbf{Passe parâmetros de classes por referência.} Passando um objeto por valor requere que este seja copiado, enquanto passando por referência não invoca um 'copy constructor'. Para objetos maiores, o desempenho pode ser aumentado em milhares de vezes com a passagem por referência;
	\item \textbf{Não declare funções do tipo 'virtual' apenas pelo fato de alguém querer dar override na mesma.} Caso seja necessário o override, é mais recomendado que o próprio programador ('overrider') mude o cabeçalho da função para 'virtual';
	\item \textbf{Colocar funções pequenas 'inline'.} Colocar funções 'inline' remove a chamada da função e o empilhamento dos parâmetros desta na pilha. É mais recomendado para funções pequenas, pois funções maiores podem gerar o 'code bloat', que consiste na produção de um código que é desnecessariamente grande, ou lento, ou que desperdiça recursos. Alguns compiladores possuem a opção de 'inline' automático para as funções menores que dado tamanho;
	\item \textbf{Declarar como 'static' as funções que não são usadas fora do arquivo.} Declarar uma função como 'static' força uma ligação interna desta com o arquivo, o que pode aumentar a performance dessa função. Se não for declarada como 'static', por 'default' é permitida uma ligação externa, que inibirá algumas otimizações como o 'inline' agressivo de alguns compiladores;
	\item \textbf{Não definir um valor de retorno se este não existe.} Isso evita que as funções passem valores de retorno quando esses não são usados.
	\end{itemize}
	
	\subsection{Condicionais e Comandos de Repetição}
	\begin{itemize}
	\item \textbf{Abrir os loops que possuem um pequeno número de repetições e um corpo de loop pequeno.} Em um loop pequeno, abri-lo remove o 'overhead' do loop, que nesses casos pode ser significativo;
	\item \textbf{Considerar a ordem das expressões enquanto codifica uma expressão lógica complexa.} Quando o compilador recebe expressões lógicas complexas, ele tenta otimizá-las fazendo com que elas terminem logo que seja possível afirmar a resposta com certeza. Por exemplo, quando temos um 'or' e um dos operandos é 'true', ou quando temos um 'and' e um dos operandos é 'false'. Portanto, a ordem em que a expressão é codificada pode aumentar o desempenho do processamento dessa expressão;
	\item \textbf{Direcionar expressões complexas de 'if' para que terminem mais rápido.} Relacionado ao item anterior, podemos manipular os comandos de 'if' para que sejam mais rápidos fazendo com que a avaliação das expressões seja mais rápidas, com base na probabilidade do que sabemos que acontece mais. Por exemplo, se queremos avaliar se dois número 'a' e 'b' estão em um determinado intervalo, podemos usar a expressão:\nl \\
	if ((a $<=$ max) \&\& (a $>=$ min) \&\& (b $<=$ max) \&\& (b $>=$ min))\\
	Se sabemos que geralmente 'a' e 'b' estarão neste intervalo. E a expressão:\nl \\
	if ((a $>$ max) $||$ (a $<$ min) $||$ (b $>$ max) $||$ (b $<$ min))\\
	Se sabemos que geralmente 'a' e 'b' estarão fora do intervalo;
	\item \textbf{Substituir 'switch' por 'if-else-if' se os valores dos 'case' do switch não não contígüos.} Quando os valores de cada 'case' do 'switch' são contígüos, o compilador os otimiza criando uma 'jump table', que reduz os 'branches' condicionais a uma única chamada de procedimento. Quando não são contígüos, o compilador cria uma densa seqüência de 'branches' condicionais, e estes podem ser substituídos por uma estrutura de 'ifs' aninhados para maior performance;
	\item \textbf{Sempre que possível, contar regressivamente até 0 (zero).} A comparação com zero pode ser feita mais rapidamente que qualquer outra comparação (algumas máquinas, como o MIPS, possuem até mesmo um registrador especial com o número zero armazenado);
	\item \textbf{Colocar os casos mais freqüentes nas primeiras posições de um 'switch'.} Fazendo isso, reduzimos o número de comparações realizadas cada vez que o programa entra nesse 'switch'. Alternativamente à opção mencionada, para o caso de alguns compiladores que não geram os 'ifs aninhados' do 'switch' na ordem em que foram colocados, pode-se usar a solução de utilizar 'switchs' aninhados, colocando os casos mais frequentes no 'switch' principal e no caso 'default' deste, um 'switch' com os casos menos freqüentes;
	\end{itemize}
	
	\subsection{Declaração, definição e atribuição}
	\begin{itemize}
	\item \textbf{Minimizar o número de variáveis locais.} Quando o número de variáveis locais é reduzido, o compilador é capaz de armazená-las todas em registradores, tornando o acesso a estas muito mais rápido comparado ao acesso pela memória, também pelo fato de o compilador não precisar empilhar estas variáveis no registrador de pilha 'stack pointer' e não precisar manipular o registrador 'frame pointer' para desempilhar. Geralmente os compiladores tentam otimizar colocando as variáveis em registradores, porém o programador pode auxiliar o compilador declarando aquelas variáveis que ele deseja colocar em registradores como 'register'. Por exemplo, um inteiro i: int register i;
	\item \textbf{Declarar variáveis locais nos escopos mais internos das funções.} Com isso, podemos impedir que variáveis fossem declaradas em escopos nos quais jamais seriam usadas;
	\item \textbf{Considerar a localidade dos dados e códigos.} O processador mantém dados ou códigos no cache, para que o acesso ocorra de forma mais rápida. Por isso, é recomendado que os dados e códigos que são utilizados em conjunto fiquem juntos também fisicamente. No C++, os dados dos objetos e seus códigos são forçados a permanecer na mesma localidade. Em C, o programador deve declarar os dados e códigos em uma ordem de forma que faça com que aqueles que são usados em conjunto fiquem juntos fisicamente;
	\item \textbf{Prefira inicialização a atribuição.} A inicialização faz com que seja chamado o construtor de um objeto e um valor final já é atribuído ao mesmo. A atribuição chama o construtor 'default' do objeto e o operador de atribuição;
	\item \textbf{Utilize as listas de inicialização dos construtores}. Quando fazemos isso, evitamos que o construtor 'default' do objeto seja chamado cada vez que fazemos uma atribuição durante a construção do mesmo;
	\item \textbf{Utilizar o modelo de atribuição 'operação='.} Quando queremos fazer uma atribuição a 'x' utilizando o valor anterior de 'x', por exemplo incrementar seu valor, devemos usar 'x += 1' ao invés de 'x = x + 1', uma vez que a segunda cria um objeto temporário;
	\item \textbf{Prefira o operador como prefixo.} A utilização de '++i' ao invés de 'i++' aumenta o desempenho. O uso do segundo força a criação de um objeto temporário, reduzindo a eficiência do código;
	\item \textbf{Utilizar a palavra-chave 'explicit'.} A palavra-chave 'explicit' força a chamada explícita de um construtor, impedindo que o programador cometa alguns erros e que o compilador construa objetos consequentes desses erros de programação;
	\end{itemize}
	
	
	\section{STL}
	\paragraph{}STL é uma biblioteca para C++ que contém \textbf{containers, algoritmos e iteradores}. É uma biblioteca genérica, baseada majoritariamente em templates; tem o aspecto positivo de que é uma biblioteca padrão, confiável, eficiente e portável, e que pode ser muito utilizada para a otimização de códigos em C++.
	
	\subsection{Containers}
	\paragraph{}Os containers são objetos que armazenam outros objetos. Na STL temos acesso aos containers \textit{vector, list, deque, set, multiset, map, multimap, hash\_set, hash\_multiset, hash\_map e hash\_multimap}. Cada uma dessas classes é um 'template' e pode ser instanciada para carregar qualquer tipo de objeto. Vamos agora descrever um pouco dessas classes de containers.
	\begin{itemize}
	\item \textbf{vector:} O \textit{vector} funciona como um vetor normal (tempo de acesso a qualquer elemento = constante), com a vantagem de poder crescer dinamicamente para conter mais elementos. Suporta a inserção e remoção no final em tempo constante, e tempo linear de inserção e remoção no começo ou meio;
	\item \textbf{list:} Representa uma lista duplamente ligada. Possui também a sua variação \textit{slist} que é uma lista encadeada simples;
	\item \textbf{deque:} Muito parecido com o \textit{vector}, com a diferença que também suporta a inserção e remoção no começo em tempo constante;
	\item \textbf{set:} Conjunto de elementos que possuem uma chave, cada elemento possui uma chave distinta. Útil para criar relações de união, intersecção e diferença entre conjuntos;
	\item \textbf{multiset:} Igual ao set, com a diferença que podem existir múltiplos elementos com a mesma chave;
	\item \textbf{map:} Parecido com o \textit{set}, associa uma chave a um tipo de dado. Cada elemento possui uma chave distinta;
	\item \textbf{multimap:} Assim como o \textit{map}, mas podem existir vários elementos com a mesma chave;
	\item \textbf{hash set, hash multiset, hash map, hash multimap:} Cria uma tabela 'hash' com as características dos containers anteriores;
	\end{itemize}
	
	\subsection{Algoritmos}
	\paragraph{}A biblioteca STL provê uma grande quantidade de algoritmos genéricos para a manipulação dos containers. Para uma lista desses algoritmos, veja o PDF em anexo.
	
	\subsection{Iteradores}
	\paragraph{}Iteradores são uma generalização para ponteiros. Eles são o mecanismo que permite separar os algoritmos dos containers. Os algoritmos são templates, parametrizados pelo tipo de iterador, portanto não ficam restritos a apenas um tipo de container. Estes iteradores são separados em cinco classes distintas:
	\begin{itemize}
	\item \textbf{InputIterator:} Permitem somente a leitura dos valores para os quais eles apontam;
	\item \textbf{OutputIterator:} Permitem apenas a escrita dos valores para os quais eles apontam;
	\item \textbf{ForwardIterator:} Podem ser \textit{constants} (permitem apenas leitura do valor) ou \textit{mutable} (permitem leitura e escrita do valor). Estes iteradores só conseguem percorrer o container em uma direção. Em rigor, são um refinamento dos InputIterator e OutputIterator (ex. de uso: listas encadeadas simples);
	\item \textbf{BidirecionalIterator:} Parecido com o ForwardIterator, mas permite percorrer o container nas duas direções (ex. de uso: listas duplamente ligadas);
	\item \textbf{RandomAccessIterator:} Permitem o acesso aleatório a uma posição do container (ex. de uso: vectors);
	\end{itemize}
	
	\bibliography{ref1}
	\nocite{*}